package com.zhupf.binarySearch;

/**
 * @author zhupf
 * @date 2024年01月17日 10:13
 * @Description
 *
 * 74. 搜索二维矩阵
 */
public class SearchMatrix {
    public static void main(String[] args) {
        int[][] matrix = {{1}};
        searchMatrix(matrix,0);
    }


    public static boolean searchMatrix(int[][] matrix, int target) {
        int up = 0;
        int down = matrix.length-1;
        int left = 0;
        int right = matrix[0].length-1;
        while (up <= down){
            int mid = up + (down - up) / 2;
            if(matrix[mid][left] <= target && target <= matrix[mid][right]){
                while (left <= right){
                    int mid2 = left + (right - left) /2;
                    if(target == matrix[mid][mid2]){
                        return true;
                    }else if (target < matrix[mid][mid2]){
                        right = mid2-1;
                    }else {
                        left = mid2+1;
                    }
                }
                return false;
            }else if(target < matrix[mid][left] ){
                down = mid-1;
            }else if(target > matrix[mid][right]){
                up = mid+1;
            }
        }
        return false;
    }

}
